/*
 *  src/algorithms/matrix_multiply.c
 *
 *  Harry Wei <harryxiyou@gmail.com> 2011 (C)
 */
#include <glib.h>
#include <stdio.h>
#include <unistd.h>

int matrix_multiply(int *p, int n, int (*m)[7], int (*s)[7])
{
#if	defined(CHECK)
	int a[3][3] = {1, 2, 3,
			4, 5, 6,
			7, 8, 9};
	int i = 0;
	int j = 0;
	int k = 0;

	for (i = 0; i < 3; i++) {
		for (j = 0; j < i; j++) {
			;
		}
		for (k = j; k < 3; k++) {
			if (3 - 1 - j >= 0) {
				printf("%d\t", a[j][k]);
			}
		}
		printf("\n");
	}
	return 0;
#endif
	int i = 0;
	int r = 0;
	int k = 0;
	int j = 0;

	for (i = 1; i <= n; i++) m[i][i] = 0;
	for (r = 2; r <= n; r++)
		for (i = 1; i <= n - r + 1; i++) {
			j = i + r - 1;
			m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++) {
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			printf("%d\t", m[i][j]);
		}
		printf("\n");
	}
	return 0;
}
